package offer2

/**
原题链接:
https://leetcode.cn/problems/chou-shu-lcof/

剑指offer 49.丑数
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。
求按从小到大的顺序的第 n 个丑数。

示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:
1 是丑数。
n 不超过1690。
*/

// 49：丑数
func nthUglyNumber(n int) int {
	//声明a,b,c下标
	a := 1
	b := 1
	c := 1

	//声明dp数组
	dp := make([]int, n+1) //方便计数, 将0下标废弃了, 所以长度为n+1
	dp[1] = 1
	//dp 1  2  3   5
	//a=3
	//b=2
	//c=2

	//从下标2开始, 分别将 *2 *3 *5的结果的较小值放入数组中
	for i := 2; i <= n; i++ {
		dp[i] = min(min(dp[a]*2, dp[b]*3), dp[c]*5)
		if dp[i] == dp[a]*2 {
			a++ //下标向后移动一位
		}
		if dp[i] == dp[b]*3 {
			b++
		}
		if dp[i] == dp[c]*5 {
			c++
		}
	}

	//返回dp[n]即可
	return dp[n]
}
